package com.zhu.heap;

import com.zhu.array.Array;

/**
 * 最大堆
 * @author: zhu
 * @date: 2019/1/16 11:11
 */
public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;//存储数据的动态数组
    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }
    public MaxHeap(){
        data = new Array<>();
    }

    /** 返回堆中元素个数 */
    public int size(){
        return data.getSize();
    }

    /** 判断堆是否为空 */
    public boolean isEmpty(){
        return data.isEmpty();
    }

    /** 计算指定索引节点的父节点的索引 */
    private int parent(int index){
        if (index == 0)
            throw new IllegalArgumentException("最顶层节点无父节点");
        return (index -1) / 2;
    }

    /** 计算指定索引的左孩子的索引 */
    private int leftChild(int index){
        return index * 2 + 1;
    }

    /** 计算指定索引的右孩子的索引 */
    private int rightChild(int index){
        return index * 2 + 2;
    }

    /** 向堆中添加元素 */
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    /**
     * 若添加的元素比父节点元素更大，就不符合完全二叉树性质，需要上浮。
     * 所谓上浮就是该元素和父节点元素交换位置。
     */
    private void siftUp(int k){
        while (k>0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
            data.swap(k,parent(k));
             k = parent(k);
        }
    }

    /** 查看堆中最大元素 */
    public E findMax(){
        if (data.getSize() == 0)
            throw new IllegalArgumentException("堆为空");
        return data.get(0);
    }

    /** 取出堆中最大元素 */
    public E extractMax(){
        E temp = findMax();
        data.swap(0,data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return temp;
    }

    /** 下沉操作 */
    private void siftDown(int k){
        while (leftChild(k) < data.getSize()){
            int j = leftChild(k);//左孩子索引
            //k节点的右孩子比左孩子大
            if (j+1 < data.getSize() && data.get(j+1).compareTo(data.get(j)) > 0){
                j = rightChild(k);//
            }
            if (data.get(k).compareTo(data.get(j)) >= 0)
                break;
            data.swap(k,j);
            k = j;
        }
    }

    /** 将最大元素替换成新元素 */
    public E replace(E e){
        E temp = findMax();
        data.update(0,e);
        siftDown(0);
        return temp;
    }

    /** heapify */
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        for (int i=parent(arr.length-1);i>=0;i--){
            siftDown(i);
        }
    }

}
